{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第13章 文本处理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**模式匹配算法（pattern matching）**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "解决问题：给出两个长度分别为n和m的字符串（n > m），在长度为n的字符串中查找长度为m的字符串。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "不同的方法：\n",
    "\n",
    "1. 穷举法\n",
    "2. Boyoer-Moore算法\n",
    "3. KMP算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**穷举法**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "思想：从索引0开始，比较n的第一个字符与m的第一个字符：如果相同，那么比较两者第二个字符；如果不同，比较n的第二个字符与m的第一个字符。重复以上过程，指导从某个索引开始，比如i索引，n的索引i字符等于m的索引0字符，直到n的索引i+m-1字符等于m的索引m-1字符，那么搜索成功，如果直到最后都没有出现这种情况，那么搜索失败。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：最坏情况下O(mn)。（比如在aaaaaaaaaaaaaaa中查找aaaab）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_brute(t, p):\n",
    "    n, m = len(t), len(p)\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i <= n - m and j < m:\n",
    "        if t[i + j] == p[j]:\n",
    "            j += 1\n",
    "        else:\n",
    "            i += 1\n",
    "            j = 0\n",
    "    if j == m:\n",
    "        return i\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "print(find_brute('aaaaaaaaaa', 'aab'))\n",
    "print(find_brute('aaaaabaaaa', 'aab'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Boyer-Moore算法**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "穷举法的缺点在于，每次只前进一步，事实上，利用一些辅助信息，有时可以前进很多步，比如一个简单的思路，用一个哈希表实现的set存储pattern的所有字符，如果在某个字符处不匹配，那么在set中查找该字符，查找不到说明可以直接前进m步。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "思想：Boyer-Moore在上面的基础上，查找该字符在pattern中最后一次出现的索引，然后跳到该索引处（如果跳到该索引是后退不是前进，那么就按照穷举法前进一步）。另外，在比较字符时，不从前往后，而是从后往前。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：肯定有所改善，但是没有明确的时间复杂度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_boyer_moore(t, p):\n",
    "    n, m = len(t), len(p)\n",
    "    last_index = {}\n",
    "    for i in range(m):\n",
    "        last_index[p[i]] = i\n",
    "    i = m - 1\n",
    "    j = m - 1\n",
    "    while i < n and j >= 0:\n",
    "        if t[i - (m - 1 - j)] == p[j]:\n",
    "            j -= 1\n",
    "        else:\n",
    "            index = last_index.get(p[j], None)\n",
    "            j = m - 1\n",
    "            if index:\n",
    "                if index >= j:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    i += j - index\n",
    "            else:\n",
    "                i += j\n",
    "    if j < 0:\n",
    "        return i - m + 1\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "print(find_boyer_moore('aaaaaaaaaa', 'aab'))\n",
    "print(find_boyer_moore('aaaaabaaaa', 'aab'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**KMP算法**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "理解KMP算法的关键：**多画图**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "之前的算法没有充分利用之前已经比较过的结果信息，KMP算法基于这一点进行改进。每次比较到达不相同的元素时，**我们获得的信息是这个元素之前pattern和长字符串的部分的是相同的**，假设往后走1步，如果要匹配成功需要之前已经匹配成功的部分（假设长度为d）的长度为d-1的前缀和后缀相同，换言之，如果不相同，那么显然走1步不可能成功。KMP算法计算了失败函数，可以知道每一次失败了最多可以走多少步可以不错过成功匹配的机会。也就是如果已匹配部分的i和i+1的前后缀都相同，那么应该选择走d-i-1步而不是d-i步，找到最长的相同的前后缀，来决定可以走的最长步数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "补充：走i步说明d-i的前后缀相等，如果知道最长相等前后缀的长度小于d-i，走i步以内都不可能匹配成功，那么只能走i步以上，走到能够匹配成功的位置。以走一步的情况来看会比较容易理解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "失败函数的计算：i表示进行到了p的哪个索引处，j表示目前已经匹配的个数，如果下一个匹配成功，那么j+1就是匹配成功的最长前后缀的长度，如果匹配失败，画出图可以看出，最长前后缀需要之前已经匹配的j长度的前后缀中，再找出匹配的前后缀，这其实也是利用了之前已经匹配成功的信息——当前字符的前一段，跟整个字符串的某段前缀是相同的。其实失败函数的计算与KMP算法的思想是一样的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：结论是O(m + n)。证明：每次循环，i和j其中之一会增大，而在限制条件下，最多n+m次循环，一定会跳出循环。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_kmp_fail(p):\n",
    "    result = [0] * len(p)\n",
    "    i = 1                               ## result的索引\n",
    "    j = 0                           \n",
    "    while i < len(p):\n",
    "        if p[i] == p[j]:                ## 如果相等，在之前j的基础上加1为最长的相同前后缀长度\n",
    "            result[i] = j + 1           \n",
    "            i += 1\n",
    "            j += 1\n",
    "        elif j > 0:                     ## 如果不等，画出图来可以看到，要想前后缀相等，需要k-1时候匹配成功的前后缀的最大相等长度\n",
    "            j = result[j - 1]\n",
    "        else:\n",
    "            i += 1\n",
    "    return result\n",
    "\n",
    "def find_kmp(t, p):\n",
    "    n, m = len(t), len(p)\n",
    "    fail_function = compute_kmp_fail(p)\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i <= n - m and j < m:\n",
    "        if t[i + j] == p[j]:\n",
    "            j += 1\n",
    "        elif j > 0:\n",
    "            i += j - fail_function[j - 1]\n",
    "            j = fail_function[j - 1]\n",
    "        else:\n",
    "            i += 1\n",
    "    if j == m:\n",
    "        return i\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "print(find_kmp('aaaaaaaaaa', 'aab'))\n",
    "print(find_kmp('aaaaabaaaa', 'aab'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**动态规划——矩阵链乘积与最长公共子序列**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动态规划使用的条件：\n",
    "\n",
    "1. 大问题的最优可以拆解为子问题的最优。\n",
    "2. 子问题存在大量重复的情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递归是动态规划的踏板，个人认为用动态规划可以解决的问题，都可以用递归解决，只是会很慢，换言之，**有些递归产生大量重复子问题的解决方案，可以使用动态规划进行改善。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "相比递归，动态规划在重复的子问题上处理得更好，如果子问题重复，动态规划只会计算一次，动态规划会使用数组或者矩阵存储计算过的子问题，然后大问题根据小问题来算。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**动态规划之矩阵链乘积**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "多个矩阵的乘积，可以适当地加括号以节省乘法运算的次数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果使用递归，将是指数级的时间复杂度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "动态规划一般是**自下而上**的，也就是先解决规模小的问题，然后逐步解决规模更大的，最后到达规模最大的问题（规模最大的问题往往就是题目的问题）。在矩阵链中，问题的规模就是矩阵的个数，用一个矩阵存储最优解，（i，j）处的元素表示第i个矩阵到第j个矩阵的连乘的最优解**（这里用一个矩阵存储是因为定义一个子问题需要i和j两个变量）**。所以j-i相当于问题规模，因此解题时，第一层循环应该是j-i从1开始增大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：$\\sum_{k=1}^{n-1} (n - k) \\times k$次，因此时间复杂度为O(n<sup>3</sup>)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrix_chain(d):               ## n个矩阵的话，d存储n+1个数，因为有n-1个长或者宽是共用的\n",
    "    n = len(d) - 1\n",
    "    result = [[0] * n for i in range(n)]\n",
    "    for k in range(1, n):          ## k是问题规模，k为1代表两个矩阵相乘\n",
    "        for i in range(n - k):     ## i是行\n",
    "            j = i + k              ## j是列\n",
    "            result[i][j] = max(result[i][t] + result[t + 1][j] + d[i] * d[t + 1] * d[j + 1] for t in range(i, j))\n",
    "    return result[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25500\n"
     ]
    }
   ],
   "source": [
    "print(matrix_chain([10, 20, 30, 25, 15]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**最长公共子序列（the longest common subsequence, LCS）**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "子序列不一定需要是连续的。假设两个字符串长度为m和n，那么使用暴力法的时间复杂度是O(2<sup>m</sup>n)，先列举出某个字符串所有可能的子序列，对于每个子序列遍历另一个字符串看是否是另一个字符串的子序列。（每个字符可以在或者不在，可能的情况有2<sup>m</sup>种）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "思路：先从递归出发，假设两个字符串分别是S1,S2，长度分别为m，n，比较两个字符串的最后一个字符，分以下情况：\n",
    "\n",
    "1. S1\\[m-1\\] = S2\\[n-1\\]: 最长公共子序列的最后一个字符一定是两个字符串的最后一个字符\\[:m-1\\]和S2\\[n-2\\]的最长公共子序列+1。\n",
    "2. S1\\[m-1\\] != S2\\[n-1\\]: 显然选出的最长公共子序列的最后一个字符可能是两个字符串最后一个字符的其中一个，也可能都不是。分类讨论来看，S1和S2的最长公共子序列可能是S1\\[:m-1\\]和S2的最长公共子序列也可能是S1和S2\\[:n-1\\]的最长公共子序列，显然就是两者的最大值。\n",
    "\n",
    "从上面的思路看，LCS问题可以用递归解决，但是运行时间可能很长。我们观察到S1\\[:m-1\\]和S2，S1和S\\[:n-1\\]两组问题递归之后可能会出现重复的子问题，如果使用递归，会重复求解相同的子问题，这点会浪费很多时间，因此使用动态规划存储已经求解好的子问题可以优化算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：使用动态规划之后，只需要搞定m\\*n的矩阵，因此时间复杂度是O(mn)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "打印LCS: 从后往前走，相等就输入，不等就得某一个索引减1，根据result比较的结果决定哪个索引减1。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCS(s1, s2):\n",
    "    m, n = len(s1), len(s2)\n",
    "    result = [[0] * m for i in range(n)]\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if s1[i] == s2[j]:\n",
    "                result[i + 1][j + 1] = result[i][j] + 1\n",
    "            else:\n",
    "                result[i + 1][j + 1] = max(result[i][j + 1], result[i + 1][j])\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCS_solution(s1, s2, result):\n",
    "    solution = []\n",
    "    i, j = len(s1), len(s2)\n",
    "    while result[i][j] > 0:\n",
    "        if s1[i - 1] == s2[j - 1]:\n",
    "            solution.append(s1[i - 1])\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        elif result[i - 1][j] >= result[i][j - 1]:\n",
    "            i -= 1\n",
    "        else:\n",
    "            j -= 1\n",
    "    return ''.join(reversed(solution))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**文本压缩**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将字符串转化为二进制，如果每个字符二进制长度固定，可能会浪费空间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Huffman编码：高频字符二进制长度短，低频字符二进制长度长，可以有效减小最终的二进制字符串长度。为了解码不产生歧义，Huffman编码是前缀码，即没有一个字符的编码是另一个字符编码的前缀。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有关解码：如果每个字符编码长度一致，那么等长解码即可；如果每个字符编码长度可能不一致，那么要求前缀码是很正常的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Huffman编码实现方法：首先计算每个字符的频率，然后构建Huffman树，先将所有字符的freq作为键放入一个优先级队列中，然后每次remove_min两次，合并，将freq相加作为新的键值，再放入优先级队列中，直到所有的都合并为一棵Huffuman树，显然每个叶子节点都是一个字符，从根节点出发到叶子节点，如果往左编码0，往右编码1可以得到每个字符的编码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "直观上理解Huffman编码算法：freq很大的很后面才合并，所以节点的深度较低，所以编码较短。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "时间复杂度：O(n + dlog(d))，n是字符串长度，d是字符去重数量；d是因为要经过d-1次合并，log(d)是因为remove_min和重新加入都是log(d)时间复杂度，n是因为要构造freq表。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "跳过Huffman编码算法最优的证明。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**字典树**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**标准字典树**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字典树解决的问题：给定字符串s和字符串的集合S，在字符串集合S中查找以字符串s为前缀的所有字符串。（字符串集合S中不存在某个字符串是另一个字符串的前缀）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字符串集合S中根据字符去重可以得到字符集合$\\Sigma$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字典树的构造：根节点无特殊含义，根节点往下一层是所有S中的字符串的第一个字母去重，然后每个字母下面的子树代表是以这个字母开头的所有字符串，即这个字母的子节点是这些字符串的第二个字母；构造完后字典树的每条到叶子节点的路径都代表S中的一个字符串。（S中的每个字符串和字典树的每个叶子节点是一一对应的）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个字典树的内部节点最多有$|\\Sigma|$个子节点，代表所有可能的后续字符。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从根节点到深度为k的节点代表所有字符串的前缀。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**KMP: 在一个长字符串中找一个短字符串。——模式匹配**\n",
    "\n",
    "**字典树：某个字符串是否是字符串集合中字符串的前缀。——词汇匹配**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有关字典树T的命题：假设要搜索的字符串是s，字符串集合S，字符集合$\\Sigma$\n",
    "\n",
    "1. T的高度为S中最长字符串的长度。\n",
    "2. T的每个内部节点最多有$|\\Sigma|$个子节点。\n",
    "3. T的叶子节点的个数为字符串集合中字符串的个数。\n",
    "4. T的节点的数目最多是n + 1个，n为S中所有字符串长度之和。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "节点数最多为n + 1发生在所有字符都不同的情况下，多出的一个节点是根节点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字典树匹配成功：匹配到叶子节点刚好s的所有字符匹配完成。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用于搜索引擎自动补全：给出的s可能搜索到某个内部节点刚好停止，然后后面所有的子树都可以作为补全，其实就是s只是字典树存储的字符串集合S中某些字符串的前缀。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搜索长度为m的字符串的运行时间：O(m$|\\Sigma|$)，m是需要搜索m层，$|\\Sigma|$是每次搜索子节点最多需要O($|\\Sigma|$)时间来遍历（如果用二级结构哈希表可以降到O(1)）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字典树的构造过程：一次插入一个字符串。插入一个字符串的时间复杂度与搜索一个字符串的时间复杂度相同。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**压缩字典树**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "标准字典树中，若某个节点仅有一个子节点，将该节点与其子节点合并。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "压缩字典树的命题：\n",
    "\n",
    "1. T的每个内部节点至少有2个子节点，至多有$|\\Sigma|$个子节点。\n",
    "2. T的叶子节点的个数与S中字符串的个数相同。\n",
    "3. T中节点的数目是O(len(S))而不是O(n)。——是因为每个内部节点至少有2个子节点，因此从根节点开始，一个外部节点至少会创造两个外部节点才成为内部节点，也就是内部节点数要+1，外部节点数至少也+1，所以内部节点数不会多于外部节点数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**如果一棵树每个内部节点至少有两个子节点，那么这棵树的外部节点数一定多于内部节点数。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**后缀字典树**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字符串集合S中的字符串是某个字符串的所有后缀，为了满足字典树没有字符串是另一个字符串的前缀的要求，在每个后缀的最后都添加一个特殊字符。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
